﻿using System;
using System.Collections.Generic;
using UnityEngine;
using System.Diagnostics;
using Debug = UnityEngine.Debug;
using Newtonsoft.Json;

namespace PathFinding
{
    public class JPSMapConfig
    {
        public int row;
        public int col;
        public float cellSize;
        public int startX;
        public int startY;
        public List<UnWalkableIndex> unWalkables;
    }
    public struct UnWalkableIndex
    {
        public int x;
        public int y;
    }

    public class JPSSeeker : ISeeker
    {
        private Grid grid;
        public JPSSeeker(Grid grid)
        {
            this.grid = grid;
        }

        //更快的contains判断
        private HashSet<Cell> closeSet = new HashSet<Cell>();
        private HashSet<Cell> openSet = new HashSet<Cell>();
        private Cell orgCell;
        private Cell endCell;

        public List<Cell> findPath(Vector2 startPos, Vector2 endPos)
        {
            int startX = this.grid.getCol(startPos.x);
            int startY = this.grid.getRow(startPos.y);
            int endX = this.grid.getCol(endPos.x);
            int endY = this.grid.getRow(endPos.y);
            if (!this.grid.isInBound(startX, startY) || !this.grid.isInBound(endX, endY))
            {
                Debug.LogError("起点or终点 不在格子内");
                return null;
            }
            Stopwatch stopwatch = new Stopwatch();
            stopwatch.Start();
            orgCell = this.grid[startX, startY];
            endCell = this.grid[endX, endY];

            closeSet.Clear();
            openSet.Clear();

            orgCell.parent = null;
            closeSet.Add(orgCell);

            Cell curCell = orgCell;
            while (!curCell.Equals(endCell))
            {
                int fromDirX = 0;
                int fromDirY = 0;
                //来的方向
                if (curCell.parent != null)
                {
                    fromDirX = clamp(curCell.parent.x - curCell.x, -1, 1);
                    fromDirY = clamp(curCell.parent.y - curCell.y, -1, 1);
                }
                for (int x = -1; x <= 1; x++)
                {
                    for (int y = -1; y <= 1; y++)
                    {
                        if ((x != 0 || y != 0) && (x != fromDirX || y != fromDirY))
                        {
                            if (x == 0 || y == 0)
                            {
                                //直线
                                Cell cell = lineFind(x, y, curCell);
                                if (cell != null)
                                {
                                    if (!closeSet.Contains(cell))
                                    {
                                        int newG = getGCostInLine(cell, curCell) + curCell.gCost;
                                        if (!openSet.Contains(cell))
                                        {
                                            cell.parent = curCell;
                                            cell.hCost = getHCost(cell, endCell);
                                            cell.gCost = newG;
                                            openSet.Add(cell);
                                        }
                                        else
                                        {
                                            if (newG < cell.gCost)
                                            {
                                                cell.parent = curCell;
                                                cell.gCost = newG;
                                            }
                                        }
                                    }
                                }
                            }
                            else
                            {
                                //斜线
                                Cell cell = biasFind(x, y, curCell);
                                if (cell != null)
                                {
                                    if (!closeSet.Contains(cell))
                                    {
                                        int newG = getGCostInBias(cell, curCell) + curCell.gCost;
                                        if (!openSet.Contains(cell))
                                        {
                                            cell.parent = curCell;
                                            cell.hCost = getHCost(cell, endCell);
                                            cell.gCost = newG;
                                            openSet.Add(cell);
                                        }
                                        else
                                        {
                                            if (newG < cell.gCost)
                                            {
                                                cell.parent = curCell;
                                                cell.gCost = newG;
                                            }
                                        }
                                    }
                                }
                            }
                        }
                    }
                }

                if (openSet.Count <= 0)
                {
                    Debug.LogError("JPS寻路失败");
                    return null;
                }

                //openSet中去最小Fcost
                var ier = openSet.GetEnumerator();
                int minCost = int.MaxValue;
                Cell newCurCell = null;
                while (ier.MoveNext())
                {
                    Cell cell = ier.Current;
                    int f = cell.gCost + cell.hCost;
                    if (f < minCost)
                    {
                        minCost = f;
                        newCurCell = cell;
                    }
                }
                openSet.Remove(newCurCell);
                closeSet.Add(newCurCell);
                curCell = newCurCell;
            }

            List<Cell> path = new List<Cell>();
            Cell loopCell = endCell;
            while (loopCell != null)
            {
                path.Add(loopCell);
                loopCell = loopCell.parent;
            }
            path.Reverse();
            stopwatch.Stop();
            Debug.LogError("JPS寻路开销 " + stopwatch.ElapsedMilliseconds);
            return path;
        }

        private bool getIsCanCross(int x, int y, int dirX, int dirY)
        {
            int horX = x - dirX;
            int horY = y - dirY;
            //可以走斜角
            //return grid.isInBound(x, y) && grid[x, y].isWalkable && ((grid.isInBound(horX, y) && grid[horX, y].isWalkable) || (grid.isInBound(x, horY) && grid[x, horY].isWalkable));
            //不能走斜角
            return grid.isInBound(x, y) && grid[x, y].isWalkable && grid.isInBound(horX, y) && grid[horX, y].isWalkable && grid.isInBound(x, horY) && grid[x, horY].isWalkable;
        }
        //斜线find
        private Cell biasFind(int dirX, int dirY, Cell curCell)
        {
            int nextX = curCell.x + dirX;
            int nextY = curCell.y + dirY;

            if (!getIsCanCross(nextX, nextY, dirX, dirY))
            {
                return null;
            }

            Cell nextCell = grid[nextX, nextY];

            if (!nextCell.isWalkable)
            {
                return null;
            }
            if (nextCell.Equals(endCell))
            {
                return nextCell;
            }
            //判断next是否为跳点
            //1.next==跳点
            Cell horCell = lineFind(dirX, 0, nextCell);
            if (horCell != null) return nextCell;
            Cell verCell = lineFind(0, dirY, nextCell);
            if (verCell != null) return nextCell;

            return biasFind(dirX, dirY, nextCell);
        }

        //直线方向找挑点
        private Cell lineFind(int dirX, int dirY, Cell curCell)
        {
            int nextX = curCell.x + dirX;
            int nextY = curCell.y + dirY;
            if (!grid.isInBound(nextX, nextY))
            {
                return null;
            }
            Cell nextCell = grid[nextX, nextY];
            if (!nextCell.isWalkable)
            {
                return null;
            }
            //判断next是否为跳点
            //1.next==跳点
            if (nextCell.Equals(endCell))
            {
                return nextCell;
            }
            //2.next有强迫邻居
            if (dirX != 0)
            {
                //上下点是否是挑点
                int upY = nextY + 1;
                if (grid.isInBound(nextX, upY))
                {
                    Cell cell = grid[nextX, upY];
                    if (cell.isWalkable && !grid[nextX - dirX, upY].isWalkable)
                    {
                        return nextCell;
                    }
                }
                int downY = nextY - 1;
                if (grid.isInBound(nextX, downY))
                {
                    Cell cell = grid[nextX, downY];
                    if (cell.isWalkable && !grid[nextX - dirX, downY].isWalkable)
                    {
                        return nextCell;
                    }
                }
            }
            else
            {
                int rightX = nextX + 1;
                if (grid.isInBound(rightX, nextY))
                {
                    Cell cell = grid[rightX, nextY];
                    if (cell.isWalkable && !grid[rightX, nextY - dirY].isWalkable)
                    {
                        return nextCell;
                    }
                }
                int leftX = nextX - 1;
                if (grid.isInBound(leftX, nextY))
                {
                    Cell cell = grid[leftX, nextY];
                    if (cell.isWalkable && !grid[leftX, nextY - dirY].isWalkable)
                    {
                        return nextCell;
                    }
                }
            }
            return lineFind(dirX, dirY, nextCell);
        }

        private int getHCost(Cell curCell, Cell endCell)
        {
            int x = Math.Abs(curCell.x - endCell.x);
            int y = Math.Abs(curCell.y - endCell.y);
            return (x + y) * 10;
            //int min = Math.Min(x, y);
            //return min * 14 + Math.Abs(x - y) * 10;
        }

        private int getGCostInLine(Cell curCell, Cell endCell)
        {
            int x = Math.Abs(curCell.x - endCell.x);
            int y = Math.Abs(curCell.y - endCell.y);
            return (x + y) * 10;
        }
        private int getGCostInBias(Cell curCell, Cell endCell)
        {
            int x = Math.Abs(curCell.x - endCell.x);
            return x * 14;
        }

        private int clamp(int value, int min, int max)
        {
            if (value < min)
                value = min;
            else if (value > max)
                value = max;
            return value;
        }

    }
}
